package com.zj.leetcode.medium.hash;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @program: algorithm
 * @description: 两数之和 II - 输入有序数组
 * 167 two-sum-ii-input-array-is-sorted
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class TwoSumIiInputArrayIsSorted {
    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        Solution solution = new TwoSumIiInputArrayIsSorted().new Solution();
        System.out.println(Arrays.toString(solution.twoSum(numbers, target)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] twoSum(int[] numbers, int target) {
            if (numbers.length <= 1) {
                return new int[]{};
            }
            int min = numbers[0];
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < numbers.length; i++) {

                if (map.containsKey(numbers[i])) {
                    return new int[]{map.get(numbers[i]) + 1, i + 1};
                }
                int temp = target - numbers[i];
                map.put(temp, i);

                if (min + numbers[i] >= target) {
                    return new int[]{};
                }
            }
            return new int[]{};
        }

        public int[] twoSum01(int[] numbers, int target) {
            int i = 0, j = numbers.length - 1;
            while (i > j) {

                int m = ((j - i) >>> 1) + i;

                if (numbers[i] + numbers[m] > target) {
                    j = m - 1;
                } else if (numbers[m] + numbers[j] < target) {
                    i = m + 1;
                } else if (numbers[i] + numbers[j] > target) {
                    j--;
                } else if (numbers[i] + numbers[j] < target) {
                    i++;
                } else {
                    return new int[]{i + 1, j + 1};
                }
            }
            return new int[]{0, 0};

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
